﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ImageProcessingLibrary
{
    unsafe class DisjointSets
    {
        #region private Fields
        private int[] sets;
        #endregion

        #region public Methods
        public DisjointSets(int totalNrOfSets)
        {
            lock (this)
            {
                this.sets = new int[totalNrOfSets];

                for (int i = 0; i < sets.Length; i++)
                {
                    sets[i] = i; //Let each set first reference itself
                }
            }
        }

        /// <summary>
        /// Finds the IdNr of the joint set (which corresponds to the lowest setIdNr in the joint set).
        /// </summary>
        /// <param name="setIdNr">The IdNr of the set which joint set we want to find.</param>
        /// <returns>The lowest IdNr of the joint sets to which "setIdNr" belongs.</returns>
        public int Find(int setIdNr)
        {
            int jointSetIdNr = sets[setIdNr];
            return jointSetIdNr;
        }
        
        /// <summary>
        /// Join the two (possibly) distinct joint sets to which set1 and set2 belong.
        /// </summary>
        /// <param name="set1IdNr">IdNr of the single set1.</param>
        /// <param name="set2IdNr">IdNr of the single set2.</param>
        public void Union(int set1IdNr, int set2IdNr)
        {
            lock (this)
            {
                int jointSetIdNr1 = sets[set1IdNr];
                int jointSetIdNr2 = sets[set2IdNr];

                if (jointSetIdNr1 == jointSetIdNr2)
                {
                    // Allready unioned. Do Nothing.
                }
                else if (jointSetIdNr1 < jointSetIdNr2)
                {
                    // All sets referencing jointSetIdNr2 must now reference jointSetIdNr1
                    for (int i = 0; i < sets.Length; i++)
                    {
                        if (sets[i] == jointSetIdNr2)
                        {
                            sets[i] = jointSetIdNr1;
                        }
                    }
                }
                else // (jointSetIdNr2 < jointSetIdNr1)
                {
                    // All sets referencing jointSetIdNr1 must now reference jointSetIdNr2
                    for (int i = 0; i < sets.Length; i++)
                    {
                        if (sets[i] == jointSetIdNr1)
                        {
                            sets[i] = jointSetIdNr2;
                        }
                    }
                }
            }
        }
        #endregion
    }
}
